#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

class MinStack {
public:
    MinStack() 
    :_size(0)
    {
        
    }
    
    void push(int val) {

        auto it = _dp.insert(val);

        _stack.emplace(_size++,it.first);

    }
    
    void pop() {
        if(!_size)
        {
            return ;
        }
        else
        {
            auto it = _stack[_size-1];
            _dp.erase(it);
            _stack.erase(--_size);
        }
    }
    
    int top() {
        if(_size)
        {
        return *_stack[_size-1];
        }
        else
        {
            return INT32_MAX;
        }
    }
    
    int getMin() {
        return *_dp.begin();
    }
    private:
    map<int,set<int>::iterator> _stack;
    set<int> _dp;
    int _size;
};
int main()
{
    MinStack stack;
    stack.push(1);
    cout<<stack.top()<<"  "<<stack.getMin();
    cout<<"\n";
    stack.push(2);
    cout<<stack.top()<<"  "<<stack.getMin();
    cout<<"\n";
    stack.push(3);
    cout<<stack.top()<<"  "<<stack.getMin();
    cout<<"\n";
    stack.push(4);
    cout<<stack.top()<<"  "<<stack.getMin();
    cout<<"\n";
    stack.push(5);
    cout<<stack.top()<<"  "<<stack.getMin();
    cout<<"\n";
    stack.pop();
    stack.pop();
    stack.pop();
    cout<<stack.top()<<"  "<<stack.getMin();
    cout<<"\n";
}
